So-called artificial intelligence or pattern-matching programming has been developing and used over the last several years, such as the RETE taught by Forgy. The RETE network is one of several approaches to pattern-matching using set(s) of matching rules. These programs are well known; see the description by Charles L. Forgy in "RETE: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem", ARTIFICIAL INTELLIGENCE, Volume 19, 1982, pp 17-37. Another example of the public knowledge in this area is found in an article by Marshall I. Schor et al. in "Advances in RETE Pattern Matching", PROCEEDINGS of 1986 AMERICAN ASSOCIATION for ARTIFICIAL INTELLIGENCE CONFERENCE, pp 226-232, 1986. The well known information about RETE algorithms and artificial intelligence programming is not repeated herein except as needed for one of ordinary skill in this art to understand the present invention.
As set forth by Forgy, the RETE algorithm exhibits certain performance advantages when large numbers of data pattern matches have to be performed. In a RETE, a rule defines one logic path of pattern matches through the network. A problem of accuracy (i.e. the RETE may generate unexpected results) can occur in certain cases. These unexpected results are such things as duplicated pattern matches (multiple rule "firings" where only one rule firing is a correct RETE response) and missing a true pattern match. Such unintended results are incorrect RETE results. It is desired to avoid unexpected pattern match results for a variety of network environmental conditions, such as pushing data changes from multiple memory nodes (this may occur when implementing dynamic rule addition to an existing RETE where it is desired to initialize the new rule with existing data, or implementing a variety of on-demand pattern matching extensions to the basic RETE algorithm), and pushing data changes through RETE structures which have been generalized to include arbitrary grouping of join structures.
As is well known, such pattern-matching programming executes with a plurality of data structures. A working memory element (WME) is an input data structure. Any new, modified or removed WME results in a "token" (or delta), which is a data structure composed of one or more WMEs together with an associated data operation. Since the current informational content of the RETE does not reflect the WME addition, change or deletion, the RETE needs to be updated by propagating the token through the network such that it reflects the current informational state of the inputs. Each time a token is pushed (processed) through a RETE and is matched with patterns in a RETE constitutes a pattern match operation.
The RETE, as taught by Forgy, consists of alpha and beta portions. When a change token is processed through the RETE, the alpha portion is first traversed after the informational content of a new or changed WME or the informational change resulting from a deleted WME is made available to a "root node". A root node is a data area of the network that is the entry point to the RETE. A set of "top" nodes are connected to the root node. These in turn are connected to successor nodes, finally reaching a plurality of termination or bottom nodes, termed production or match nodes. Each of the node data structures may include match tests for incoming tokens. As known in the art, some of the nodes have memory items to be scanned in a table. These may be implemented as separate nodes, termed "memory nodes", or the tables may be directly associated with nodes representing match operations. The associated memory table for a particular node will be referred to as that node's "result memory". Result memory tables are associated with beta nodes and alpha distribution nodes which will be described later.
The tables for memory items contain values (numeric, text, etc.) which represent partial matching results up to that point in the network. These values may be used in subsequent matching operations as one of the inputs to a "join" node. It is to be understood that table accesses follow usual programming procedures and that the matching operations are usual programming effected comparisons.
The alpha portion of a RETE has no result memories, i.e. tables wherein partial pattern matching results are stored; in contrast the beta portion includes such memory tables. In between the alpha and beta portions are nodes called alpha distribution nodes, all of which have result memories which store the partial pattern matching results generated in the alpha portion. From these alpha distribution nodes, the tokens are pushed into the beta portion.
Some of the RETE nodes have one input while other RETE nodes have two inputs. All alpha nodes (as do later described production nodes or match nodes) have one input as do the alpha distribution nodes. Such one inputs are herein referred to as an "RHS input" or simply "input". In contrast, most beta nodes, except production nodes, match nodes, and other special purpose nodes, have two inputs: one input is a left hand side (LHS) input and the other input is a right hand side (RHS) input. Such two input nodes are called "join nodes"; token pairs (consisting of a token as an input from each side of the node (LHS and RHS) are subjected to join tests of such join node (which may be no test at all). If a join test is successful (or no test), it is said the token inputs are joined together, resulting in new amalgamated tokens which are used to update the associated result memory table of the join node.
Execution of a RETE algorithm starts with a change token, representing the addition, modification, or deletion of a WME, and scans a plurality of alpha nodes. Each alpha node tests various aspects of the WME as represented by the token, and passes or blocks (does not pass) the token on to various successors nodes (hereafter successors) of the alpha node. A successor node is a node that receives an input from the current node; a predecessor node is a node which supplies an input to the current node.
This updating continues, as is well known in the prior art, until the bottom of the alpha portion is reached. At this point, the first result memory at the logical bottom of the alpha portion (the alpha distribution node) receives the token, and may update its memory in accordance with the particular WME and operation (add, modify, or delete). Following these pattern matching operations, the beta portion of the RETE continues the RETE operations. For each token arriving at one input of a prototypical beta join node, such node specifies pattern matching functions between the token contents at the one input (either LHS or RHS) and a set of partially matched tokens contained in the result memory found at the predecessor node which supplies inputs to the input of such join node at the opposite input to the one input. The partial matching results and the token contents are compared using tests defined in such join node.
In OPS5, the possible structure of the RETE network is strictly limited to so-called "linear and left associative" updating. Consequently, pattern matching operations in OPS5 work only in such limited RETE structures. That is, the resultant output from join nodes goes only to the LHS input of successor join nodes. The term "predecessor" and "successor" nodes defines the logical relationship of the nodes. A predecessor node to a given node means that the output of the predecessor node becomes an input to the given node. A successor node to the given node receives its output as an input; for a join node, this input may be received at either the LHS or RHS input. In the "linear and left associative" RETE structure, join node outputs which are connected to successor join nodes are connected to the LHS input of successor join nodes, only. The RHS input to all join nodes is from alpha distribution nodes.
As set forth by Schor et al., supra, it is desirable to generalize the structure of RETE to allow any arbitrary match patterns. In a Schor et al generalized RETE, tokens from predecessor join nodes as well as alpha distribution nodes also can be supplied to the RHS input of a join node. Thus, a join node can receive inputs at LHS and RHS inputs from two different or identical predecessor join nodes. Further, the RETE structure enabled by the present invention can be non-linear, e.g. binary, and have any diverse associative characteristics.
A node is called "self-joined" whenever one of its outputs is joined with an output of itself or its immediate or non-immediate successors. In OPS5 the only possible node type of the selfjoined nodes is the alpha distribution node, while in the generalized RETE there are no such restrictions.
In OPS5, when a token is pushed from a node having an associated memory, such as a beta join node, the RETE algorithm scans successor nodes in a certain order to which output tokens are to be pushed. For the successors which are connected as LHS inputs, the order of scanning is a later defined ascending order (scan starting from a logically remote node to nearer nodes). This ascending scan is a known OPS5 operation.
In generalized RETE structure, unlike in OPS5, tokens may be generally supplied to either of the two nodal inputs, LHS or RHS, from nodes having result memories, including beta join nodes. It has been found that applying the scanning algorithm used in OPS5 may produce unexpected results (errors) under environmental conditions referred to above. It is desired to avoid such errors and extend the successful and correct operations of matching networks to include variable environmental conditions. SUMMARY OF THE INVENTION
The present invention provides for accurate match network updating irrespective of diverse environmental changes or actions of a pattern-match network; this provision enables generalization of pattern-match network structure and operation. In this invention, a RETE network is to be updated by sending tokens from a set of so-called "stop nodes". In accordance with the invention, not all portions of the RETE have to be updated by each addition, change or deletion of input information from a working memory. Stop nodes are designated in the network to stop the updating from reaching predetermined ones of the nodes; such stop nodes are updated. All nodes which are not updated are members of a second portion of the network termed "suspended" portion signifying that such predetermined nodes have not been updated to the latest network update. One or more suspended portions may exist in the second portion and each suspended portion has one or more stop nodes logically attached thereto. Each suspended portion is connected to the rest of the RETE for selectively receiving tokens through the stop nodes. Resume nodes heading the suspended portion are immediate successors to the respective stop nodes, each stop node may have one or more resume nodes.
Each suspended portion is selectively updated by successive scans of the nodes in the suspended portion. The node scanning sequence from each of stop nodes is determined in part by the arrangement of the resume nodes in the suspended portion. In updating the suspended portion, from each stop node ascending and descending scans of its successor nodes in the suspended portion provide for accurate updating of such nodes. The scanning of the suspended portion nodes from a plurality of stop nodes is a repetition of the ascending and descending scans from the respective stop nodes connected to the one suspended portion.
The present invention enables a pattern matching network to be generalized and to have different states of memory node updating without introducing unexpected pattern matching results. Other applications of a stop node function are within the scope of the present invention.
The foregoing and other objects, features, and advantages of the invention will be apparent from the following more particular description of preferred embodiments of the invention, as illustrated in the accompanying drawing.